package com.peng.old.sort;

import java.util.Arrays;

public class RadixSort {

    public static void main(String[] args) {
        int[] arr = new int[]{43, 50, 46, 50, 30};
//        sort(arr);
        int digitCount = findMaxNumNumericalDigit(arr);
//        System.out.println(Math.pow(10,-1));
//        sort2(arr, digitCount);
        msdRadixSort(arr, 0, arr.length-1, digitCount);

        System.out.println(Arrays.toString(arr));


    }

    /**
     * 低位优先算法
     *
     * @param arr
     */
    public static void sort(int[] arr) {
        int digitCount = findMaxNumNumericalDigit(arr);
        int[] result = new int[10];
        int[] count = new int[10];
        for (int i = 0; i < digitCount; i++) {
            int pow = (int) Math.pow(10, i);
            for (int j = 0; j < arr.length; j++) {
                int num = arr[j] / pow % 10;//得到对应“位”上的数, 它是一个0-9的数字
                count[num]++;
            }

            //累加数组，保证稳定性
            for (int k = 1; k < count.length; k++) {

                count[k] = count[k] + count[k - 1];
            }

            for (int j = arr.length - 1; j >= 0; j--) {
                int num = arr[j] / pow % 10;//得到对应“位”上的数, 它是一个0-9的数字
                result[--count[num]] = arr[j];
            }
            System.arraycopy(result, 0, arr, 0, arr.length);
            Arrays.fill(count, 0);//将桶重新进行清空，以便下一轮进行统计
        }


    }

    /** 高位， 未完成
     * @param arr
     * @param digit 第几位
     * @return
     */
    public static int[][] sort2(int[] arr, int digit) {

        if(digit<=0){
            return new int[0][];
        }


        int[] result = new int[arr.length];
        int[] count = new int[10];

        int[][] resultArr = new int[10][arr.length];
        int pow = (int) Math.pow(10, digit-1);
        if(pow==0){
            System.out.println(123);
        }

        for (int j = 0; j < arr.length; j++) {
            int num = arr[j] / pow % 10;//得到对应“位”上的数, 它是一个0-9的数字
            resultArr[num][count[num]] = arr[j];
            count[num]++;
        }

        for (int k = 0; k < count.length; k++) {

            if (count[k] > 1) {
                sort2(resultArr[k], digit - 1);
            }

        }

        //累加数组，保证稳定性
        for (int k = 1; k < count.length; k++) {

            count[k] = count[k] + count[k - 1];
        }

        for (int j = arr.length - 1; j >= 0; j--) {
            int num = arr[j] / pow % 10;//得到对应“位”上的数, 它是一个0-9的数字
            result[--count[num]] = arr[j];
        }
        System.arraycopy(result, 0, arr, 0, arr.length);


        return resultArr;








    }

    /**
     * 高位
     * @param arr
     * @param begin
     * @param end
     * @param d
     */
    public static void msdRadixSort(int[] arr,int begin, int end, int d){
        int radix = 10;
        int[] count = new int[10];
        int pow = (int) Math.pow(10, d-1);
        //分配木桶
        int[]bucket = new int[end-begin+1];
        //统计各木桶的需要装 元素的个数
        for (int i = begin; i <= end; i++) {
            int num = arr[i] / pow % 10;//得到对应“位”上的数, 它是一个0-9的数字
            count[num]++;
        }
        //统计 每一个木桶存放的位置  末位置
        for (int i = 1; i < radix; i++){
            count[i] = count[i] + count[i - 1];
        }
        ///这里从右向左扫，保证稳定性
        for (int i = end; i >= begin; i--){
            int num = arr[i] / pow % 10;//得到对应“位”上的数, 它是一个0-9的数字
            bucket[--count[num]] = arr[i] ;//   放入木桶
        }

        //收集木桶数据
        for (int i = begin,j = 0; i <= end; i++ ,j++){
            arr[i] = bucket[j];
        }

        // 对各个桶中的数据进行再排序
        for (int i = 0; i < radix; i++) {
            int p1 = begin + count[i]; //第i个桶的左边界
            int p2; //第i个桶的右边界

            if (i < radix-1){
                p2 = begin + count[i + 1] - 1;

            }else{
                p2 = end;
            }

            if (p2>p1 && d>1){ //木桶里有两个数以上，且d>1（数位大于个位）
                msdRadixSort(arr, p1, p2, d-1); // 对桶递归调用，进行基数排序，数位降1
            }

        }

    }

    private static int findMaxNumNumericalDigit(int[] arr) {
        if (arr.length == 0) {
            throw new RuntimeException("数组为空");
        }
        int maxNum = findMaxNum(arr);
        int digit = 0;
        for (int i = maxNum; i > 0; i /= 10) {
            digit++;
        }
        return digit;

    }

    private static int findMaxNum(int[] arr) {
        if (arr.length == 0) {
            throw new RuntimeException("数组为空");
        }
        int maxNum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxNum) {
                maxNum = arr[i];
            }
        }
        return maxNum;
    }

}
